1. Field of the Invention
The present invention relates to a method and an apparatus for decoding an error correcting code, and more specifically, it relates to a method and an apparatus for decoding an error correcting code such as a BCH (Bose-Chaudhuri-Hocquenghem) code employed for detecting and correcting a bit error in received data in a digital data transmission system such as an automobile telephone system, a cordless telephone or satellite broadcasting.
2. Description of the Prior Art
In transmission of digital data, a bit error is generally caused by deterioration in the S-N ratio or distortion of the transmission system. In a general method of coping with such a bit error, redundant bits having error correcting ability (hereinafter referred to as error correcting bits) are previously added to original information bits, to be subjected to transmission. On the data sink side, a bit error position is detected on the basis of the received error correcting bits, to be corrected. Among such error correcting codes, the BCH code, having high error correcting ability with respect to length (bit number) of the correcting bits, is widely employed for transmission of a control signal in an automobile telephone system or a cordless telephone in Japan or U.S., or in a digital data transmission system such as PCM (pulse code modulation) audio broadcasting by satellite.
Description is briefly made on detection/correction of a bit error in transmission data through the BCH code. On the data source side, error correcting bits are obtained on the basis of original information bits and a prescribed generator polynominal G(X) to be added to the original information bits, and subjected to transmission. On the data sink side, a received signal train V(X) is divided by the said generator polynominal, thereby to find the remainder term S(X) thereof. This remainder term S(X) is hereinafter referred to as a syndrome. Presence/absence of a bit error is judged on the basis of the syndrome S(X), to detect the error position. Then bit error correction is performed by inverting the value of the bit corresponding to the detected error position.
FIG. 1 typically illustrates basic structure for data transmission in an automobile telephone system employing such a BCH code. Referring to FIG. 1, each terminal 1 is connected to a base station 3 through an exchange 2. High frequency radio communication in a scope of 800 to 900 MHz is performed between the base station 3 and a mobile station 4, while, in particular, control between the both stations such as origination, paging and channel switching is performed by transmission of digital signals. According to AMPS (advanced mobile phone service) specification for an automobile telephone system in the U.S., original information bits are transmitted with addition of the BCH code in transmission of digital signals for such control. In more concrete terms, according to the AMPS specification, a first control signal from the base station 3 to the mobile station 4 and a second control signal from the mobile station 4 to the base station 3 both employ the BCH code obtained on the basis of the original information bits and a generator polynominal G(X)=X.sup.12 +X.sup.10 +X.sup.8 +X.sup.5 +X.sup.4 +X.sup.3 +1. On the data source side, a bit train of zeros in a number equal to the degree of the generator polynominal (i.e., 12) is added to the original information bits so as to follow the least significant bit thereof. Then the original information bits with the bit train of zeros are divided by the generator polynominal G(X), to find the remainder R(X). This remainder R(X) is added to the original information bits so as to follow the least significant bit thereof, to be subjected to transmission.
According to the aforementioned AMPS specification, for example, the code length of the first control signal thus transmitted is 40 bits and the code length of the second control signal is 48 bits while minimum distance of codes is 5 in each case. Thus, it is possible to provide double-bit error correcting ability, while erroneous correction may be caused in this case. Therefore, the AMPS specification is restricted only to single-bit error correcting ability (primary correction), to improve ability for preventing erroneous correction.
In order to perform primary correction of the received data to which the BCH code is added, the received signal train V(X) is generally divided by the generator polynominal G(X) to first obtain the remainder term, i.e., the syndrome S(X). If the value of the syndrome S(X) is zero, i.e., when the received signal train V(X) is exactly divisible by the generator polynominal G(X), a judgement is made that no bit error is caused. On the other hand, if the value of the syndrome S(X) is not zero, i.e., when the received signal train V(X) is not divided out by the generator polynominal G(X), a judgement is made that a single-bit error or a multiple-bit error is caused in the process of data transmission. A ROM table storing previously calculated values of bit error positions corresponding to syndrome values in occurrence of single-bit errors is so prepared as to obtain the corresponding bit error position from the ROM table with the address of the obtained value of the syndrome S(X). Such technique is disclosed in Transactions of IECE Japan, Feb. 1979, Vol. J62-B No. 2, "Bit Error Rate Reduction Performance of BCH Codes and Self-Orthogonal Convolutional Codes" by K. Koga et al., for example.
According to the above described method, however, capacity required for the ROM is 2.sup.k bytes assuming that k represents the degree of the generator polynominal (in the case of of code length of within 255 bits. If the code length exceeds 255 bits, the capacity is further increased). In the aforementioned AMPS specification, the degree of the generator polynominal is 12, and hence 2.sup.12 =4098 bytes are required as the capacity for the ROM. On the other hand, the code length of the received signal is 48 bits even in the longer second control signal, and hence the number of error positions in occurrence of a primary error is 48.
Thus, according to the conventional error correcting method as hereinabove described, the required ROM capacity is too far increased as compared with the number of the primary error correcting positions, to deteriorate availability of the ROM.